package com.yulongtian.oneProblemEveryDay.month202301;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/
 * 自己写的可以通过任意情况，但是超时
 * 官方解答是二分查找
 *
 * @author yulongTian
 * @create 2023-01-04 13:54
 */
public class Test03 {
    public static void main(String[] args) {
        System.out.println(maxValue(6, 4, 395252961));
    }

    public static int maxValue(int n, int index, int maxSum) {
        if (n == maxSum) {
            return 1;
        }
        int[] nums = new int[n];
        Arrays.fill(nums, 1);

        int curSum = n;
        while (curSum < maxSum) {
            nums[index]++;
            curSum++;
            int left = index - 1;
            int right = index + 1;
            while (curSum < maxSum) {
                if (left < 0 && right >= n) {
                    break;
                }
                //向左
                if (left >= 0) {
                    nums[left]++;
                    left--;
                    curSum++;
                }

                if (curSum >= maxSum) {
                    break;
                }

                //向右
                if (right < n) {
                    nums[right]++;
                    right++;
                    curSum++;
                }

                if (curSum >= maxSum) {
                    break;
                }
                if (check(nums, left, right)) {
                    break;
                }

            }
            if (curSum >= maxSum) {
                break;
            }
        }
        return nums[index];
    }

    //判断是否满足abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
    public static boolean check(int[] nums, int left, int right) {
        if (left < 0) {
            //看右边
            if (right >= nums.length) {
                return true;
            } else {
                if (right - 1 >= 0) {
                    return Math.abs(nums[right - 1] - nums[right]) <= 1;
                }
            }
        }

        if (right >= nums.length) {
            //看左边
            if (left < 0) {
                return true;
            } else {
                if (left + 1 < nums.length) {
                    return Math.abs(nums[left] - nums[left + 1]) <= 1;
                }
            }
        }

        return Math.abs(nums[left] - nums[left + 1]) <= 1 && Math.abs(nums[right - 1] - nums[right]) <= 1;
    }

    //官方解答
//    public int maxValue(int n, int index, int maxSum) {
//        int left = 1, right = maxSum;
//        while (left < right) {
//            int mid = (left + right + 1) >>> 1;
//            if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
//                left = mid;
//            } else {
//                right = mid - 1;
//            }
//        }
//        return left;
//    }
//
//    private long sum(long x, int cnt) {
//        return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;
//    }

}
